package mashibing.class7;

import java.util.*;

/**
 * 带索引的堆（自定义比较器)
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-03-30
 */
public class Class7_2_Heap<T> {

    public List<T> heap;
    public int heapSize;
    public Map<T, Integer> indexMap;
    public Comparator<? super T> comp;

    public Class7_2_Heap(Comparator<? super T> comp) {
        heap = new ArrayList<>();
        heapSize = 0;
        indexMap = new HashMap<>();
        this.comp = comp;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public int getSize() {
        return heapSize;
    }

    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    public T peek() {
        return heap.get(0);
    }

    public void push(T t) {
        heap.add(t);
        indexMap.put(t, heapSize);
        heapInsert(heapSize++);
    }

    public void heapify(Integer index) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int larges = (left + 1 < heapSize) && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? left + 1 : left;
            larges = comp.compare(heap.get(index), heap.get(larges)) < 0 ? index : larges;
            if (index == larges) {
                break;
            }
            swap(index, larges);
            index = larges;
            left = index * 2 + 1;
        }
    }

    public void heapInsert(Integer index) {
        while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public void resign(T obj) {
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

    public T pop() {
        T t = heap.get(0);
        swap(0, heapSize - 1);
        indexMap.remove(t);
        heap.remove(--heapSize);
        heapify(0);
        return t;
    }

    public void remove(T t) {
        if (!indexMap.containsKey(t)) {
            System.out.println("无该元素");
            return;
        }
        T replace = heap.get(heapSize - 1);
        int index = indexMap.get(t);
        indexMap.remove(t);
        heap.remove(--heapSize);
        if (replace != t) {
            heap.set(index, replace);
            indexMap.put(replace, index);
//            resign(replace);
            heapInsert(index);
            heapify(index);
        }
    }

    // 请返回堆上的所有元素
    public List<T> getAllElements() {
        List<T> ans = new ArrayList<>();
        for (T c : heap) {
            ans.add(c);
        }
        return ans;
    }

    public void swap(int index1, int index2) {
        T t1 = heap.get(index1);
        T t2 = heap.get(index2);
        indexMap.put(t1, index2);
        indexMap.put(t2, index1);
        heap.set(index2, t1);
        heap.set(index1, t2);
    }
}
